Search Results

Documents authored by Prakash, Anupam

Document
DOI: 10.4230/LIPIcs.ESA.2018.66
On Learning Linear Functions from Subset and Its Applications in Quantum Computing

Authors: Gábor Ivanyos, Anupam Prakash, and Miklos Santha

Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)

Abstract
Let F_{q} be the finite field of size q and let l: F_{q}^{n} -> F_{q} be a linear function. We introduce the Learning From Subset problem LFS(q,n,d) of learning l, given samples u in F_{q}^{n} from a special distribution depending on l: the probability of sampling u is a function of l(u) and is non zero for at most d values of l(u). We provide a randomized algorithm for LFS(q,n,d) with sample complexity (n+d)^{O(d)} and running time polynomial in log q and (n+d)^{O(d)}. Our algorithm generalizes and improves upon previous results [Friedl et al., 2014; Gábor Ivanyos, 2008] that had provided algorithms for LFS(q,n,q-1) with running time (n+q)^{O(q)}. We further present applications of our result to the Hidden Multiple Shift problem HMS(q,n,r) in quantum computation where the goal is to determine the hidden shift s given oracle access to r shifted copies of an injective function f: Z_{q}^{n} -> {0, 1}^{l}, that is we can make queries of the form f_{s}(x,h) = f(x-hs) where h can assume r possible values. We reduce HMS(q,n,r) to LFS(q,n, q-r+1) to obtain a polynomial time algorithm for HMS(q,n,r) when q=n^{O(1)} is prime and q-r=O(1). The best known algorithms [Andrew M. Childs and Wim van Dam, 2007; Friedl et al., 2014] for HMS(q,n,r) with these parameters require exponential time.
Cite as

Gábor Ivanyos, Anupam Prakash, and Miklos Santha. On Learning Linear Functions from Subset and Its Applications in Quantum Computing. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 66:1-66:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{ivanyos_et_al:LIPIcs.ESA.2018.66,
  author =	{Ivanyos, G\'{a}bor and Prakash, Anupam and Santha, Miklos},
  title =	{{On Learning Linear Functions from Subset and Its Applications in Quantum Computing}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{66:1--66:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-081-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{112},
  editor =	{Azar, Yossi and Bast, Hannah and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.66},
  URN =		{urn:nbn:de:0030-drops-95299},
  doi =		{10.4230/LIPIcs.ESA.2018.66},
  annote =	{Keywords: Learning from subset, hidden shift problem, quantum algorithms, linearization}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2017.49
Quantum Recommendation Systems

Authors: Iordanis Kerenidis and Anupam Prakash

Published in: LIPIcs, Volume 67, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)

Abstract
A recommendation system uses the past purchases or ratings of n products by a group of m users, in order to provide personalized recommendations to individual users. The information is modeled as an m \times n preference matrix which is assumed to have a good rank-k approximation, for a small constant k. In this work, we present a quantum algorithm for recommendation systems that has running time O(\text{poly}(k)\text{polylog}(mn)). All known classical algorithms for recommendation systems that work through reconstructing an approximation of the preference matrix run in time polynomial in the matrix dimension. Our algorithm provides good recommendations by sampling efficiently from an approximation of the preference matrix, without reconstructing the entire matrix. For this, we design an efficient quantum procedure to project a given vector onto the row space of a given matrix. This is the first algorithm for recommendation systems that runs in time polylogarithmic in the dimensions of the matrix and provides an example of a quantum machine learning algorithm for a real world application.
Cite as

Iordanis Kerenidis and Anupam Prakash. Quantum Recommendation Systems. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 49:1-49:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{kerenidis_et_al:LIPIcs.ITCS.2017.49,
  author =	{Kerenidis, Iordanis and Prakash, Anupam},
  title =	{{Quantum Recommendation Systems}},
  booktitle =	{8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
  pages =	{49:1--49:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-029-3},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{67},
  editor =	{Papadimitriou, Christos H.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.49},
  URN =		{urn:nbn:de:0030-drops-81541},
  doi =		{10.4230/LIPIcs.ITCS.2017.49},
  annote =	{Keywords: Recommendation systems, quantum machine learning, singular value estimation, matrix sampling, quantum algorithms.}
}
Document
DOI: 10.4230/LIPIcs.CCC.2016.17
On the Sum-of-Squares Degree of Symmetric Quadratic Functions

Authors: Troy Lee, Anupam Prakash, Ronald de Wolf, and Henry Yuen

Published in: LIPIcs, Volume 50, 31st Conference on Computational Complexity (CCC 2016)

Abstract
We study how well functions over the boolean hypercube of the form f_k(x)=(|x|-k)(|x|-k-1) can be approximated by sums of squares of low-degree polynomials, obtaining good bounds for the case of approximation in l_{infinity}-norm as well as in l_1-norm. We describe three complexity-theoretic applications: (1) a proof that the recent breakthrough lower bound of Lee, Raghavendra, and Steurer [Lee/Raghavendra/Steurer, STOC 2015] on the positive semidefinite extension complexity of the correlation and TSP polytopes cannot be improved further by showing better sum-of-squares degree lower bounds on l_1-approximation of f_k; (2) a proof that Grigoriev's lower bound on the degree of Positivstellensatz refutations for the knapsack problem is optimal, answering an open question from [Grigoriev, Comp. Compl. 2001]; (3) bounds on the query complexity of quantum algorithms whose expected output approximates such functions.
Cite as

Troy Lee, Anupam Prakash, Ronald de Wolf, and Henry Yuen. On the Sum-of-Squares Degree of Symmetric Quadratic Functions. In 31st Conference on Computational Complexity (CCC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 50, pp. 17:1-17:31, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{lee_et_al:LIPIcs.CCC.2016.17,
  author =	{Lee, Troy and Prakash, Anupam and de Wolf, Ronald and Yuen, Henry},
  title =	{{On the Sum-of-Squares Degree of Symmetric Quadratic Functions}},
  booktitle =	{31st Conference on Computational Complexity (CCC 2016)},
  pages =	{17:1--17:31},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-008-8},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{50},
  editor =	{Raz, Ran},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2016.17},
  URN =		{urn:nbn:de:0030-drops-58383},
  doi =		{10.4230/LIPIcs.CCC.2016.17},
  annote =	{Keywords: Sum-of-squares degree, approximation theory, Positivstellensatz refutations of knapsack, quantum query complexity in expectation, extension complexity}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact